package com.company.linkedList;

import java.util.Stack;
/**
 * 反转链表
 * */
public class RevertLinkedList {

    public static ListNode buildSampleList() {
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i = 1; i < 5; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }
        return head;
    }

    public ListNode solution(ListNode head) {
//        return function1(head);
//        return function2(head);
        return function3(head);
    }


    /**
     * 第一种方法 遍历更改每一个元素的 next 指向
     */
    private ListNode function1(ListNode head) {
        ListNode pre;
        ListNode cur;
        ListNode next;

        pre = null;
        cur = head;

        while (cur != null) {
            next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;
        }
        return pre;
    }

    /**
     * 使用栈的方法进行翻转
     */
    public ListNode function2(ListNode head) {
        ListNode node = head;
        Stack<ListNode> stack = new Stack<>();
        while (node != null) {
            stack.push(node);
            node = node.next;
        }

        ListNode result = null;
        while (!stack.isEmpty()) {
            node = stack.pop();
            if (result == null) {
                result = node;
            }
            node.next = stack.isEmpty() ? null : stack.peek();
        }
        return result;
    }

    /**
     * 使用头插法进行反转
     */

    public ListNode function3(ListNode head) {

        ListNode newHead = null;
        ListNode node = null;
        ListNode next = null;

        //移动到新节点上
        newHead = head;
        node = head.next;
        newHead.next = null;
        //记录当前操作元素


        while (node != null) {
            next = node.next;
            node.next = newHead;

            newHead = node;
            node = next;
        }
        return newHead;
    }
}
